package com.Offer;

import com.pojo.TreeNode;

import java.util.Stack;

/*
    面试题27：二叉树的镜像
    操作给定的二叉树，将其变换为源二叉树的镜像。
    测试用例：
        8
       / \
      6   10
     / \  / \
    5  7 9   11
 */
public class demo27 {

    public static void main(String[] args) {

    }

    //递归
    public static boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        return isMirror(root.left,root.right);
    }

    public static boolean isMirror(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }

        if(left == null || right == null){
            return false;
        }
        return left.val == right.val && isMirror(left.left,right.right) && isMirror(left.right,right.left);
    }

    /*------------------------------------------------------*/
    //循环
    public static boolean isSymmetric2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode t1 = stack.pop();
            TreeNode t2 = stack.pop();
            if(t1 == null && t2 == null){
                continue;
            }
            if(t1 == null || t2 == null){
                return false;
            }
            if(t1.val != t2.val){
                return false;
            }
            stack.push(t1.left);
            stack.push(t2.right);
            stack.push(t1.right);
            stack.push(t2.left);
        }
        return true;
    }



}
